#include <mpi.h>
#include <stdio.h>
#include <limits>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <set>
#include <conio.h>
#include <vector>
#include <conio.h>
#include <math.h>
#include <cmath>
#include <time.h>
#include <iomanip>
#include <cstdlib>
#include <memory>
#include <stdarg.h>

using namespace std;
#define _CRT_SECURE_NO_DEPRECATE
#define NAZEV "test.txt";

class Uzel {
    int nazevUzlu; //nazev(cislo)uzlu
    int stupenUzlu;
    int i;

    Uzel** spojeneUzly; //pole ukazatelu na okolni uzly (primo spojene hranou)
    int pocetSpojenychUzlu; //pocet okolnich uzlu
public:
    //inicializace uzlu

    Uzel(int stupen, int nazev = -1) : nazevUzlu(nazev), pocetSpojenychUzlu(0) {
        stupenUzlu = stupen;

        spojeneUzly = (Uzel**) malloc(sizeof (Uzel*) * stupen); //pole ukazatelu na okolni uzlu velikosti stupne
        //jmeno je -1 pokud neni nastaveno a pocet okolnich uzlu 0
        i = 0;
        while (i < stupenUzlu) {
            spojeneUzly[i] = 0;
            i++;
        }
    }

    void setJmeno(int name) {
        nazevUzlu = name;
    }

    void addSpojeneUzly(Uzel* an) {//pokud jsou dva uzly spojene hranou prida dany uzel
        //cout << "pridavam uzel " << an->getNazevUzlu() << " k uzlu " << getNazevUzlu() << endl;
        spojeneUzly[pocetSpojenychUzlu++] = an;
    }

    int getNazevUzlu() {
        return nazevUzlu;
    }

    void zobrazUzel() {
        cout << "od: " << nazevUzlu << " do: ";
        for (int i = 0; i < pocetSpojenychUzlu; i++) {
            cout << spojeneUzly[i]->getNazevUzlu() << " ";
        }
    }

    Uzel** getSpojeneUzly() {
        return spojeneUzly;
    }

    int getpocetSpojenychUzlu() {
        return pocetSpojenychUzlu;
    }

    ~Uzel() {
        delete[] spojeneUzly;
        spojeneUzly = 0;
    }
};

class Graf {
    Uzel** uzly;
    int pocetUzlu;
    int stupenUzlu;
public:

    Graf(int n, int k, char* file) {
        pocetUzlu = n;
        stupenUzlu = k;
        uzly = (Uzel**) malloc(n * sizeof (Uzel*)); //inicializace pole ukazatelu na Uzel
        // cout <<  sizeof (Uzel*);

        for (int i = 0; i < pocetUzlu; i++) {
            uzly[i] = new Uzel(k, i);
        }

        int cisloUzlu = 0;
        int pocetRadku = 0;

        string line;
        ifstream stream(file);
        /*if (!stream.is_open()) {
            cout << "Nepodarilo se otevrit soubor" << endl;
        } else {
            cout << "Soubor nacten" << endl;
        }*/

        stream.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //vynechani prvni radky
        while (getline(stream, line)) {
            ++pocetRadku;
            for (int i = 0; i < line.size(); i++) {
                if (line[i] == '1') {
                    // cout << nodeNum;
                    uzly[cisloUzlu]->addSpojeneUzly(uzly[i]);
                }
            }
            cisloUzlu++;
        }
        //cout << " +soubor nacten\n";

    }

    void print() {
        for (int i = 0; i < pocetUzlu; i++) {
            uzly[i]->zobrazUzel();
            cout << "\n";
        }
    }

    Uzel* getUzelPodleCisla(int num) {
        return uzly[num];
    }

    // *********Jak se bude implementovat deleni na tzv. intervaly*********

    uint64_t getCombinations(unsigned int n, unsigned int k) {
        if (k > n)
            return 0;
        uint64_t r = 1;
        for (unsigned int d = 1; d <= k; ++d) {
            r *= n--;
            r /= d;
        }
        return r;
    }

    // pocetProcesoru se zjisti pomoci MPI_Comm_size

    uint64_t interval(int pocetProcesoru, int velikostPografu) {
        uint64_t velikostIntervalu = ceil(getCombinations(this->pocetUzlu, velikostPografu) / pocetProcesoru); // pozor, posledni bude mensi (kvuli zaokrouhleni nahoru)
        return velikostIntervalu;
    }

    ~Graf() {
        delete[] uzly;
        uzly = 0;
    }

};

int getMaxK(char* file) {
    int avaiUzelNum = 0, maxK = 0;
    string line;
    ifstream stream(file);
    /*if (!stream.is_open()) {
        cout << "Nepodarilo se otevrit soubor" << endl;
    } else {
        cout << "Soubor nacten" << endl;
    }*/

    stream.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //preskoceni prvni radky
    while (getline(stream, line)) {
        for (size_t i = 0; i < line.size(); i++) {
            if (line[i] == '1') {
                avaiUzelNum++;
            }
            if (maxK < avaiUzelNum) {
                maxK = avaiUzelNum;
            }
        }
        avaiUzelNum = 0;
    }
    return maxK;
}

bool next_subset(vector<int> & v, int n) {
    /* VSTUP: vzestupne setridena k-prvkova podmnozina prvku z {0, 1, ..., n-1},
     * kde 0 <= k <= n.

     * VYSTUP: v se prepise na lexikograficky nejblizsi nasledujici k-prvkovou
     * podmnozinu mnoziny {0, 1, ..., n-1} a funkce vrati true. Jestlize vsak
     * takova podmnozina neexistuje, funkce vrati false.
     */
    vector<int>::reverse_iterator it;
    for (it = v.rbegin(); it < v.rend(); ++it)
        if (*it < --n) {
            n = ++*it;
            while (it > v.rbegin())
                *--it = ++n;
            return true;
        }
    return false;
}

int getBW(Graf& g, set<int> s, int bestBW) {
    int value = 0, pocetDostupnychUzlu;
    Uzel* n;
    Uzel** dostupneUzly;
    set<int>::iterator iter;
    //pro vsechny jmena uzlu v mnozine s
    for (iter = s.begin(); iter != s.end(); iter++) {
        n = g.getUzelPodleCisla(*iter); //najdi a vrat uzel z grafu g odpovidajici jmenu(cislu)
        dostupneUzly = n->getSpojeneUzly(); //vrat mnozinu dostupnych uzlu z uzlu n
        pocetDostupnychUzlu = n->getpocetSpojenychUzlu(); //vrat pocet dostupnych uzlu z uzlu n
        //pokud neni uzel v mnozine zvysime BW o 1
        for (int i = 0; i < pocetDostupnychUzlu; i++) {
            if (s.count(dostupneUzly[i]->getNazevUzlu()) == 0)value++;
            // ukoncim rezani, pokud je uz bisekcni sirka vetsi nez zatim nejlepsi bisekcni sirka
            if (value > bestBW) {
                return value;
            }
        }

    }
    return value;
}

class Log {
    ofstream logTXT;
public:

    Log(int processRank) {
        char logTXT[255];
        sprintf(logTXT, "log-rank%d.txt", processRank);
        this->logTXT.open(logTXT, std::ios_base::out | std::ios_base::app);
        if (this->logTXT.good()) {
            //http://www.cplusplus.com/reference/clibrary/ctime/localtime/

            time_t rawtime;
            struct tm * timeinfo;
            char buffer [80];

            time(&rawtime);
            timeinfo = localtime(&rawtime);

            strftime(buffer, sizeof (buffer), "%c", timeinfo);
            this->logTXT << endl << "Log started at: " << buffer << endl;
        }
    }

    ~Log() {

        this->logTXT.close();
    }
public:

    void ladeni(string zprava) {
        if (this->logTXT.good()) {

            this->logTXT << setw(6) << clock() << " ***Ladeni*** " << zprava << endl;
        }
    }

    void chyba(string zprava) {
        if (this->logTXT.good()) {

            this->logTXT << setw(6) << clock() << " ***Chyba*** " << zprava << endl;
        }
    }

    void upozorneni(string zprava) {
        if (this->logTXT.good()) {

            this->logTXT << setw(6) << clock() << " ***Upozorneni*** " << zprava << endl;
        }
    }

    void info(string zprava) {
        if (this->logTXT.good()) {

            this->logTXT << setw(6) << clock() << " ***Info*** " << zprava << endl;
        }
    }

    void info(const char* format, ...) {
        char result[255];

        va_list listPointer;
        va_start(listPointer, format);

        vsprintf(result, format, listPointer);
        this->info(string(result));
        va_end(listPointer);
    }

    void ladeni(const char* format, ...) {
        char result[255];

        va_list listPointer;
        va_start(listPointer, format);

        vsprintf(result, format, listPointer);
        this->ladeni(string(result));
        va_end(listPointer);
    }

    void chyba(const char* format, ...) {
        char result[255];

        va_list listPointer;
        va_start(listPointer, format);

        vsprintf(result, format, listPointer);
        this->chyba(string(result));
        va_end(listPointer);
    }
};

class MPIpar {
public:
    int rank;
    int pocetProcesoru;
    int dalsiProcesor;
    int predchoziProcesor;
    int velikostPodgrafu;
    Log* log;
    Graf* graf;
    uint64_t velikostIntervalu;
    int maxK;

    enum Stav {
        /// <summary>
        /// Initial state
        /// </summary>
        State_Offline,

        /// <summary>
        /// Worker is currently solving chunk of work.
        /// </summary>
        State_Working,

        /// <summary>
        /// Checking incoming messages.
        /// </summary>
        State_Chatting,

        /// <summary>
        /// Requesting work from neighbour.
        /// </summary>
        State_Asking,

        /// <summary>
        /// Waiting for response from neighbour.
        /// </summary>
        State_Waiting,

        /// <summary>
        /// Terminating process.
        /// </summary>
        State_Quitting
    };
    Stav stav;
    /// <summary>
    /// Time of creation of the object.
    /// </summary>
    double startTime;

public:

    MPIpar(int velikostPodgrafu) {
        this -> inicializace();
        this->log->info("Vytvarim graf.");
        this->maxK = getMaxK("c:/test.txt");
        this->log->info("Maximalni stupen uzlu je: %d", maxK);
        this->graf = new Graf(20, maxK, "c:/test.txt");
        this->velikostPodgrafu = velikostPodgrafu;
    }

    void inicializace() {
        this->startTime = MPI_Wtime();

        MPI_Comm_size(MPI_COMM_WORLD, &this->pocetProcesoru);
        MPI_Comm_rank(MPI_COMM_WORLD, &this->rank);

        this->log = new Log(this->rank);
        this->log->ladeni("Inicializace");

        this->stav = State_Offline;

        this->dalsiProcesor = (this->rank + 1) % this->pocetProcesoru; // vedlejsi procesor
        this->predchoziProcesor = this->rank == 0 ? this->pocetProcesoru - 1 : (this->rank - 1) % this->pocetProcesoru;
        this->log->info("Inicializace probehla. Rank: %d, velikost: %d, predchozi: %d, dalsi: %d", this->rank, this->pocetProcesoru, this->predchoziProcesor, this->dalsiProcesor);
    }

    void setup() {
        this->log->info("Pocatecni nastaveni");

        MPI_Barrier(MPI_COMM_WORLD);

        if (this->rank == 0) {
            velikostIntervalu = this->graf->interval(pocetProcesoru, velikostPodgrafu);
            this->log->ladeni("Broadcastuji velikost intervalu: %llu", velikostIntervalu);
            MPI_Bcast(&velikostIntervalu, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
        } else {
            this->log->ladeni("Získávám velikost intervalu.");
            MPI_Bcast(&velikostIntervalu, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
            this->log->ladeni("Velikost intervalu je: %llu", velikostIntervalu);
        }
    }

    int bc(int n, int k) {
        int result = 1;
        int m;
        if (n - k < k) {
            m = k;
            k = n - k;
        } else
            m = n - k;

        for (int i = 1; i <= k; ++i)
            result = result * (m + i) / i;

        return result;
    }

    void spust() {
        set<int>::iterator iter;
        int tag;
        int bestBW = this->maxK * 20;
        set<int> bestSet;
        set <int> mySet;
        // Vektor v inicializujeme na lexikograficky minimalni k-prvkovou
        // podmnozinu mnoziny {0, 1, ..., n-1}, tj. v = {0, 1, ..., k-1}.
        vector<int> v;
        vector<int> subset;
        uint64_t pocatecniInterval = velikostIntervalu * this->rank;
        uint64_t pomVelikostIntervalu = this->velikostIntervalu;


        this->log->ladeni("Pocatecni interval je: %llu", pocatecniInterval);
        this->log->ladeni("Max bw: %d", bestBW);

        int j = 0;
        uint64_t pomPocatecniInterval = pocatecniInterval;
        int n = 20;
        int tmp;
        while (velikostPodgrafu--) {
            while (pomPocatecniInterval >= (tmp = bc(--n, velikostPodgrafu))) {
                ++j;
                pomPocatecniInterval -= tmp;
            }
            subset.push_back(j++);
        }
        

        cout << subset[0] << " " << subset[1] << " " << subset[2];
        
        cout << "Pomocna velikost intervalu: " << pomVelikostIntervalu << "\n";

        // udelam pocet kombinaci jako je velikost intervalu
        while (pomVelikostIntervalu--) {
            mySet.clear(); // na zacatku musime pomocnou mnozinu vymazat
            copy(subset.begin(), subset.end(), inserter(mySet, mySet.end())); // zkopirovani vector<int> do set<int>
            set<int>::iterator iter2;
            int pom = getBW(*(this->graf), mySet, bestBW);
            if (pom < bestBW) {
                bestBW = pom;
                bestSet = mySet;
            }
            if (!next_subset(subset, 20)) {
                break;
            }
        }

        this->log->ladeni("Nejlepsi bw procesoru c.%d: %d", this->rank, bestBW);
    }

    int getRank() {
        return this->rank;
    }

    int getPocetProcesoru() {
        return this->pocetProcesoru;
    }

};

int main(int argc, char * argv[ ]) {
    MPIpar* mpiPar;
    MPI_Init(&argc, &argv);
    int velikostPodgrafu = 3;

    mpiPar = new MPIpar(velikostPodgrafu);
    mpiPar->setup();
    mpiPar->spust();

    MPI_Finalize();

    return 0;
}